#include <math.h>
#include <stdio.h>
#include <stdlib.h>
char const* RESULT = "_result.txt";

char *get_outputfile_name(int argc, char const *argv[]);
void do_main(char const* inputfile, char const* outputfile);
void liner_reg(int n, double x[], double y[], double *a, double *b);

int main(int argc, char const *argv[])
{
	char *outputfile = 0;
	if (argc < 2)
	{
		fprintf(stderr, "usage: %s inputfile [outputfile]\n", argv[0]);
		exit(0);
	}
	outputfile  = get_outputfile_name(argc, argv);
	//printf("outputfile is :%s\n", outputfile);

	do_main(argv[1], outputfile);

	if (outputfile != 0)
	{
		free(outputfile);
	}	
	return 0;
}

/*
*  
*  输入文件格式：
*  node1 node2
*  ...
*/
#define BUF_SIZE 4096000
char buff[BUF_SIZE];
void do_main(char const* inputfile, char const* outputfile)
{
	int degree_size = 4096000;
	int node_size, edge_size, max_degree;
	double degree_avg;
	int *degree = (int *) malloc(sizeof(int) * degree_size);
	double *y, *x, a, b;
	FILE *in = fopen(inputfile,"r"), *out = fopen(outputfile, "r");
	
	memset(degree, 0, degree_size * sizeof(int));

	printf("start file read!\n");
	while (fgets(buff, BUF_SIZE, in) != NULL) {
		int node1, node2;
		//printf("%s\n", buff);
		sscanf(buff, "%d %d", &node1, &node2);
		/*if (degree_size < fmax(node1, node2))
		{
			printf("realloc\n");
			int max_node = fmax(node1, node2);
			max_node = fmax(max_node, 2 * degree_size);
			degree = realloc(degree, max_node * sizeof(int));
			memset(degree + degree_size, 0, (max_node - degree_size) * sizeof(int));
			degree_size = max_node;
		}*/
		degree[node1] ++;
		degree[node2] ++;
	}

	printf("file read over!\n");
	node_size = edge_size = max_degree = 0;
	int degree_total = 0;
	for (int i = 0; i < degree_size; i ++) {
		if (degree[i] > 0)
			node_size ++;
		edge_size += degree[i];
		max_degree = fmax(max_degree, degree[i]);
		degree_total += degree[i];
	} 
	edge_size /= 2;
	degree_avg = edge_size * 2.0 / node_size;


	
	int *n = (int*)malloc(max_degree * sizeof(int));//度为n的顶点数量
	int *k = (int*)malloc(max_degree * sizeof(int));//度序列
	memset(n, 0, max_degree * sizeof(int));
	int l = 0;//度序列长度
	int total_n = 0;
	for (int i = 1; i < node_size; i ++)
	  if (degree[i] > 0) {
	    n[degree[i] - 1] ++;
	    total_n ++;
	  }
	int max_n = 0;
	for (int i = 0; i < max_degree; i ++) {
	  if (n[i] > 0) {
	    k[l++] = i + 1;
	  }
	}

	//	printf("max_degree = %d, degree_total = %d, total_n=%d\n",
	//     max_degree, degree_total,total_n);
	printf("N = %d, M = %d, A = %f, l = %d",
	       node_size, edge_size, degree_avg, l);
	printf(", log2(N)=%f, n1=%d, n4=%d, kl=%d, nkl=%d\n", 
	       log2(node_size), n[0], n[3],k[l-1], n[k[l-1]-1] );

	/*
	* p(k) = a * k^(-r)  log p(k) = -r * log k + log a
	*/
	x = (double*) malloc(max_degree * sizeof(double));
	y = (double*) malloc(max_degree * sizeof(double));
	memset(y, 0, max_degree * sizeof(double));
	for (int i = 0; i < l; i ++) {
	  x[i] = log(i + 1);
	  y[i] = log(k[i]);	
	}
	liner_reg(l, x, y, &a, &b);
	printf("b = %f\n", b);
}
char *get_outputfile_name(int argc, char const *argv[])
{
	char *outputfile;
	if (argc < 3)
	{
		char const *inputfile = argv[1];
		int i = strlen(inputfile) - 1;
		while (i >= 0 && inputfile[i] != '.') i--; 
		outputfile = (char*) malloc(sizeof(char) * (strlen(inputfile) + strlen(RESULT)));
		strncpy(outputfile, inputfile, i);
		strcpy(outputfile + i, RESULT);
	} else {
		outputfile = (char*) malloc(sizeof(char) * strlen(argv[2]));
		strcpy(outputfile, argv[2]);
	}	
	return outputfile;
}

/**
*最小二乘法线性回归
*y=a + bx
*/
void liner_reg(int n, double x[], double y[], double *a, double *b)
{
	double x_avg, y_avg;
	double sum_upper, sum_lower;
	int i;
	//for (int i = 0; i < n; i += n / 100) printf("%f, %f\n", x[i], y[i]);
	x_avg = y_avg = 0.0;
	for (i = 0; i < n; i ++) {
		x_avg += x[i];
		y_avg += y[i];
	}
	//printf("x_avg = %f, y_avg = %f\n", x_avg, y_avg);
	x_avg /= n;
	y_avg /= n;

	sum_upper = sum_lower = 0.0;
	for (i = 0; i < n; i ++) {
		sum_upper += (x[i] - x_avg) * (y[i] - y_avg);
		sum_lower += (x[i] - x_avg) * (x[i] - x_avg);
	}
	//printf("sum_upper = %f, sum_lower = %f\n", sum_upper, sum_lower);
	*b = sum_upper / sum_lower;
	*a = y_avg - x_avg * (*b);
}
